package class06;

import java.util.Comparator;
import java.util.PriorityQueue;

// 测试链接：https://leetcode.com/problems/merge-k-sorted-lists/
public class Code01_MergeKSortedLists {

	public static class ListNode {
		public int val;
		public ListNode next;
	}

	public static class ListNodeComparator implements Comparator<ListNode> {

		@Override
		public int compare(ListNode o1, ListNode o2) {
			return o1.val - o2.val; 
		}

	}

	/**
	 * 复杂度:
	 * 假设M条链表, 总节点个数N
	 * 小根堆大小为M, 小根堆操作复杂度为 O(logM)
	 * 一共进出小根堆N次
	 * O(N*logM)
	 * 链表数组(内含多个有序链表), 需将多个有序链表合并成一个有序链表
	 * 1 4 6
	 * 2 3 7
	 * 5 5 9
	 * 使用小根堆, 先将头全部插入, 默认最小可以最先弹出
	 * 弹出最小值, 加入list, 然后把next加入小根堆中排序
	 * 再弹出排序后的最小值, 加入list, 把next加入小根堆中
	 * 周而复始
	 *
	 * @param lists
	 * @return
	 */
	public static ListNode mergeKLists(ListNode[] lists) {
		if (lists == null) {
			return null;
		}
		PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
		for (int i = 0; i < lists.length; i++) {
			if (lists[i] != null) {
				//先把头部节点添加到小根堆
				heap.add(lists[i]);
			}
		}
		if (heap.isEmpty()) {
			return null;
		}
		//弹出一个最小值
		ListNode head = heap.poll();
		ListNode pre = head;
		if (pre.next != null) {
			//取出最小值的下一个值, 放入小根堆中排序
			heap.add(pre.next);
		}
		//小根堆不为空
		while (!heap.isEmpty()) {
			//弹出一个最小
			ListNode cur = heap.poll();
			//list的下一个值指向弹出值, 以获得一个有序大链表
			pre.next = cur;
			//重新定位到next节点
			pre = cur;
			if (cur.next != null) {
				//把弹出节点的下一个节点加入小根堆
				heap.add(cur.next);
			}
		}
		return head;
	}

}
